# NOTE: rewritten from: http://gameprogrammingstepbystep.blogspot.com/2011/04/midpoint-displacement-algorithm-example.html
# *
# * It works! :D
# *


import random

size = 200
maxvalue = 128
map = [[0 for i in range(size)] for j in range(size)]


def doMidPoint():
    map[0][0] = maxvalue
    map[size - 1][0] = maxvalue
    map[size - 1][size - 1] = maxvalue
    map[0][size - 1] = maxvalue
    midpoint(0, 0, (size - 1), (size - 1))
    
def midpoint(x1, y1, x2, y2):
    
    if(x2 - x1 < 2) and (y2 - y1 < 2):
        return
       
    dist = x2 - x1 + y2 - y1
    hdist=dist / 2
    
    # Find Middle Point
    midx = (x1 + x2) / 2
    midy = (y1 + y2) / 2
    
    # Get pixel colors of corners
    c1 = map[x1][y1]
    c2 = map[x2][y1]
    c3 = map[x2][y2]
    c4 = map[x1][y2]
    
    # If Not already defined, work out the midpoints of the corners of
    # the rectangle by means of an average plus a random number.
    if map[midx][y1] == 0:
        map[midx][y1] = (c1 + c2 + random.randint(0, dist) - hdist) / 2
         
    if map[midx][y2] == 0:
        map[midx][y2] = (c4 + c3 + random.randint(0, dist) - hdist) / 2
        
    if map[x1][midy] == 0:
        map[x1][midy] = (c1 + c4 + random.randint(0, dist) - hdist) / 2
        
    if map[x2][midy] == 0:
        map[x2][midy] = (c2 + c3 + random.randint(0, dist) - hdist) / 2

    # Work out the middle point...
    map[midx][midy] = (c1 + c2 + c3 + c4 + random.randint(0, dist) - hdist) / 4

    # Now divide this rectangle into 4, And call again For Each smaller
    # rectangle
    midpoint(x1, y1, midx, midy)
    midpoint(midx, y1, x2, midy)
    midpoint(x1, midy, midx, y2)
    midpoint(midx, midy, x2, y2)
    
    
doMidPoint()

#import matplotlib.pyplot as plt

#plt.imshow(map)
#plt.show()


#for row in map:
#    print row